package Algorithm.Array.MinSubArrayLen;

/**
 * @Author ykeezy
 * @Date：2024/6/811:44
 * @PacakageName：
 * @ClassName：2024/6/8
 * @Description：209长度最小子数组
 * @Version 1.0
 */
class MinSubArrayLen {

    //给定一个含有 n 个正整数的数组和一个正整数 target 。
    //
    //找出该数组中满足其总和大于等于 target 的长度最小的
    //子数组
    // [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    //双指针——滑动窗口法
    //时间复杂： O（n）
    //快指针向右移动累加sum等待sum >= target，若找到，则在慢指针和快指针这个区间继续寻找有无更小的子串
    //在寻找无有更小子串：慢指针向右移动并从sum减去自己刚刚指向的元素以求满足条件的更小的子串，并根据情况更新result
    // 一旦条件不满足 sum >= target，停止移动，并交给快指针继续向后探
    public static int DoublePointerminSubArrayLen(int target, int[] nums){
        //符合条件数组的长度,注意初始值的设定，最好是设定为nums.length() + 1
        int result = nums.length + 1;
        //慢指针——起始指针
        int slowPointer = 0;
        //子串总和
        int sum = 0;
        //fastpointer——快指针——终止指针
        for (int fastPointer = 0; fastPointer <= nums.length - 1 ; fastPointer++) {
            sum += nums[fastPointer];
            //若子串和 >= target，则result记录并扫描这个子串里有无符合要求的更小子串
            if (sum >= target){
                //fastPointer - slowPointer + 1 -> 子串长度
                //若新符合要求的子串长度 < result则更新result
                result = Math.min(result, (fastPointer - slowPointer + 1));
                //扫描这个子串里有无符合要求的更小子串
                while (slowPointer <= fastPointer){
                    //慢指针向快指针移动扫描子串
                    sum -= nums[slowPointer++];
                    if (sum >= target){
                        result = Math.min(result, (fastPointer - slowPointer + 1));
                    }else {
                        break;

                    }

                }

            }

        }

        //result == nums.length()则说明没有符合要求的子串，return 0;
        return result == nums.length + 1 ? 0 : result;

    }

    //暴力解法
    //暴力法在某些参数写会超时(过不了LEETCODE)
    //以外层循环的outter为起始下标，内层inner从outter开始向数组右边累加sum并检查是否 >= target
    //若sum >= target，则比对当前result决定是否更新这个result，完成后跳出内层循环开始下一次外层循环
    //之所以一满足sum >= target就跳出循环是因为更右边的情况会随着outter向右移动全部检查到，所以不需要inner继续向右检查
    //时间复杂度 O(n^2)
    public static int RangeminSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        for (int outter = 0;  outter <= nums.length - 1 ; outter++) {
            int sum = 0;
            for (int inner = outter; inner <= nums.length - 1; inner++) {
                sum += nums[inner];
                if (sum >= target){
                    result = Math.min(result, (inner - outter + 1));
                    break;

                }

            }

        }


        return result == nums.length + 1 ? 0 : result;

    }

    //

    public static void main(String[] args) {
        System.out.println(DoublePointerminSubArrayLen(7,new int[]{2,3,1,2,4,3}));
        System.out.println(RangeminSubArrayLen(7,new int[]{2,3,1,2,4,3}));

    }

}
